/*
 * Sorter.java
 *
 * Created on 2008/12/28 +0900
 *
 * $Revision: 59 $
 * $Date: 2008-12-28 19:22:21 +0000 (Sun, 28 Dec 2008) $
 */

package org.gikolet.framework.util;

import java.util.Vector;

/**
 * @author Tetsutaro (latest modification by $Author: tetsutaro.ss $)
 * @version $Revision: 59 $ $Date: 2008-12-28 19:22:21 +0000 (Sun, 28 Dec 2008) $
 */
public final class Sorter {

    private Sorter() {
    }

    public static void sort(int[] array) {
	sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int left, int right) {
	int p = array[(left + right) / 2];
	int i = left;
	int j = right;

	while (true) {
	    while (array[i] < p) {
		i++;
	    }

	    while (array[j] > p) {
		j--;
	    }

	    if (i >= j) {
		break;
	    }

	    swap(array, i, j);

	    i++;
	    j--;
	}

	if (left < --i) {
	    sort(array, left, i);
	}

	if (right > ++j) {
	    sort(array, j, right);
	}
    }

    public static void sort(Vector vector, Comparator comparator) {
	sort(vector, comparator, 0, vector.size() - 1);
    }

    private static void sort(Vector vector, Comparator comparator, int left,
	    int right) {
	Object p = vector.elementAt((left + right) / 2);
	int i = left;
	int j = right;

	while (true) {

	    while (comparator.compare(vector.elementAt(i), p) < 0) {
		i++;
	    }

	    while (comparator.compare(vector.elementAt(j), p) > 0) {
		j--;
	    }

	    if (i >= j) {
		break;
	    }

	    swap(vector, i, j);

	    i++;
	    j--;
	}

	if (left < --i) {
	    sort(vector, comparator, left, i);
	}

	if (right > ++j) {
	    sort(vector, comparator, j, right);
	}
    }

    public static void swap(int[] intArray, int i, int j) {
	Assert.isTrue(0 <= i);
	Assert.isTrue(i < intArray.length);

	Assert.isTrue(0 <= j);
	Assert.isTrue(j < intArray.length);

	int tmp = intArray[i];
	intArray[i] = intArray[j];
	intArray[j] = tmp;
    }

    public static void swap(Vector vector, int i, int j) {
	Assert.isTrue(0 <= i);
	Assert.isTrue(i < vector.size());

	Assert.isTrue(0 <= j);
	Assert.isTrue(j < vector.size());

	Object tmp = vector.elementAt(i);
	vector.setElementAt(vector.elementAt(j), i);
	vector.setElementAt(tmp, j);
    }
}
